package mop.util.sort;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;



/**
 * MergeSort implementation
 * @author MOP Team 7
 */
public class MergeSort<T> implements Sort<T> {

	/**
	 * The comparator
	 */
	private Comparator<T> comparator;
	
	/**
	 * @see Sort#sort(List, Comparator)
	 */
	@Override
	public void sort(List<T> list, Comparator<T> comparator) {
		this.comparator = comparator;
		List<T> tmpArray = new LinkedList<T>();
		for(int i = 0; i < list.size(); i++){
			tmpArray.add(null);
		}
	    mergeSort( list, tmpArray, 0, list.size() - 1 );
	}

    /**
     * Internal method that makes recursive calls.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param left the left-most index of the subarray.
     * @param right the right-most index of the subarray.
     */
    private void mergeSort( List<T> a, List<T> tmpArray,
            int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center );
            mergeSort( a, tmpArray, center + 1, right );
            merge( a, tmpArray, left, center + 1, right );
        }
    }
    
    /**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private void merge( List<T> a, List<T> tmpArray,
            int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd )
            if( comparator.compare(a.get(leftPos),a.get(rightPos)) <= 0)
            	tmpArray.set(tmpPos++, a.get(leftPos++));
            else
            	tmpArray.set(tmpPos++, a.get(rightPos++));
        
        while( leftPos <= leftEnd )    // Copy rest of first half
        	tmpArray.set(tmpPos++, a.get(leftPos++));
        
        while( rightPos <= rightEnd )  // Copy rest of right half
        	tmpArray.set(tmpPos++,a.get(rightPos++));
        
        // Copy tmpArray back
        for( int i = 0; i < numElements; i++, rightEnd-- )
        	a.set(rightEnd,tmpArray.get(rightEnd));
 
    }

}
